function Node(data, left, right) {
    this.data = data;
    this.left = left;
    this.right = right;
}

Node.prototype = {
    show: function () {
        // console.log(this.data);
        return this.data
    }
}

const Tree = function () {
    this.root = null;
}

// const preArr = []
// const midArr = []
// const lasterArr = []

Tree.prototype = {
    preArr : [],
    midArr : [],
    lasterArr: [],
    // 二叉树的生成操作 insert方式是一个一个插入
    insert: function (data) {
        let node = new Node(data, null, null);
        if (!this.root) {
             // 如果根节点就是本身那将把根节点赋值即可 
            this.root = node;
            return;
        }
        let current = this.root;
        let parent = null;
        // 循环插入
        while (current) {
            parent = current;
            if (data < parent.data) {
                //如果数值大 则插入左树
                current = current.left;
                  // 循环到当前没有值时 跳出循环
                if (!current) {
                    parent.left = node;
                    return;
                }
            } else {
                //如果数值大 则插入左树
                current = current.right;
                // 循环到当前没有值时 跳出循环
                if (!current) {
                    parent.right = node;
                    return;
                }
            }

        }
    },
      // 前序
    preOrder: function (node) {
        if (node) {
            this.preArr.push(node.show());
            this.preOrder(node.left);
            this.preOrder(node.right);
        }
        return this.preArr
    },
    // 中序
    middleOrder: function (node) {
        if (node) {
            this.middleOrder(node.left);
            this.midArr.push(node.show());
            this.middleOrder(node.right);
        }
        return this.midArr
    },
    // 后序
    laterOrder: function (node) {
        if (node) {
            this.laterOrder(node.left);
            this.laterOrder(node.right);
            this.lasterArr.push(node.show())
        }
        return this.lasterArr
    },
    //取最小值
    getMin: function () {
        var current = this.root;
        while(current){
            if(!current.left){
                return current;
            }
            current = current.left;
        }
    },
    //取最大值
    getMax: function () {
        var current = this.root;
        while(current){
            if(!current.right){
                return current;
            }
            current = current.right;
        }
    },
    // 获取树的深度
    getDeep: function (node,deep) {
        deep = deep || 0;
        if(node == null){
            return deep;
        }
        deep++;
        let dleft = this.getDeep(node.left,deep);
        let dright = this.getDeep(node.right,deep);
        return Math.max(dleft,dright);
    },

       // 树的查找
    getNode: function (data,node){
        if(node){
            if(data === node.data){
                return node
            }else if(data < node.data){
                return this.getNode(data,node.left)
            }else{
                return this.getNode(data,node.right)
            }
        }else {
            return null;
        }
    }
}

    // 使用方式
    let t =new Tree();
    t.insert(3);
    t.insert(8);
    t.insert(1);
    t.insert(2);
    t.insert(5);
    t.insert(7);
    t.insert(6);
    t.insert(0);
    // t 就是树
    // console.log(t);
    // t.middleOrder(t.root);
    console.log(t.getMax());
    console.log(t.getDeep(t.root, 0));
    console.log(t.getNode(5,t.root));
    // console.log(t.preOrder(t.root));


    // 二分查找
 function binarySearch(data,arr,start,end){
    if(start > end){
        return -1
    }
    let mid = Math.floor((end+start)/2);
    if(data == arr[mid]){
        return mid;
    }else if(data < arr[mid]){
        return binarySearch(data,arr,start,mid-1)
    }else{
        return binarySearch(data,arr,mid+1,end)
    }
 }
 const arr = [0,1,1,1,1,1,1,1,1,4,6,7,89,6]
 // 如果是相同的值则找到的是中间那位  比如1 出现的就是中间的第六位
 // 如果第一次出现 比如 4 出现时第九位 比如 6 第一次出现在 第10位
//  console.log(binarySearch(6,arr,0,arr.length-1));
 
 export {Tree,Node}